Sort Characters By Frequency || Top K Frequent Elements

发表于

Sort Characters By Frequency

Question

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

1
2
3
4
5
6
7
8
9
**Input:**
"tree"
**Output:**
"eert"
**Explanation:**
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

1
2
3
4
5
6
7
8
9
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

1
2
3
4
5
6
7
8
9
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Analysis

  1. O(n)解法
    • 利用map记录出现在string中的各字符的次数
    • List Array的脚标i表示该字符在String中出现的次数，List以string的形式存储char，方便后续脚标从大到小遍历。 注意在新建ArrayList之后还需向其中加入当前字符ch，所以不能用else
    • 根据脚标从大到小遍历，将字符以脚标个数加入字符串中
  2. 利用Bucket Sort解决该问题
    • ASCII码字符共有256个，故利用数组记录不同字符的出现次数
    • 构造maxcount+1个String桶，将出现了相同次数的字符放入String桶中
    • 同上进行遍历

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public String frequencySort(String s) {
        if(s.length()<3)    return s;
        Map<Character,Integer> map=new HashMap<>();
        int max=0;
        for(Character ch:s.toCharArray()){
            map.put(ch,map.getOrDefault(ch,0)+1);
            max=Math.max(max,map.get(ch));
        }
        
        //Get List
        List<Character>[] str=new List[max+1];
        for(Character ch:map.keySet()){
            int tmp=map.get(ch);
            if(str[tmp]==null)  
                str[tmp]=new ArrayList();
            str[tmp].add(ch);		//Should not use else
        }
        
        //Get result string
        StringBuilder res=new StringBuilder();
        for(int i=max;i>0;i--){
            List<Character> list=str[i];
            if(list!=null){
                 for(Character ch:list){
                    for(int j=0;j<i;j++){
                        res.append(ch);
                    }
                }
            }
        }
        return res.toString();
    }
}

Bucket Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public String frequencySort(String s) {
        int[] count=new int[256];
        int max=0;
        for(char c:s.toCharArray()){
            count[c]++;
            max=Math.max(max,count[c]);
        }
        String[] bucket=new String[max+1];
        for(int i=0;i<256;i++){
            String tmp=bucket[count[i]];
            if(count[i]>0){
                bucket[count[i]]=(tmp==null)?""+(char)i:(tmp+(char)i);
            }
        }
        StringBuilder res=new StringBuilder();
        for(int i=max;i>=0;i--){
            if(bucket[i]!=null){
                for(char c:bucket[i].toCharArray()){
                    for(int j=0;j<i;j++){
                        res.append(c);
                    }
                }
            }
        }
        return res.toString();
    }
}

Top K Frequent Elements

Question

Given a non-empty array of integers, return the k most frequent elements.

For example,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Analysis

同上，在找kth元素的时候利用count计数，满足条件跳出循环

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        List<Integer> res=new ArrayList();
        int max=0;
        //Count the freq of num
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
            max=Math.max(max,map.get(i));
        }
        //Get the list which index is the freq
        List<Integer>[] list=new List[max+1];
        for(Integer i:map.keySet()){
            int freq=map.get(i);
            if(list[freq]==null)
                list[freq]=new ArrayList();
            list[freq].add(i);
        }
        //Return the top Kth
        int count=1;
        for(int i=max;i>=0;i--){
            List<Integer> tmp=list[i];
            if(count>k)     break;
            if(tmp!=null){
                for(Integer num:tmp){
                    if(count<=k){
                        res.add(num);
                        count++;
                    }
                    else 
                        break;
                }
            }
        }
        return res;
    }
}